package net.xuele.learn.dancing;

import java.util.Arrays;

/**
 * @Author: yubo
 * @date: 13:50 2020/12/18
 * @Description: 类描述
 */

public class ReadMe {

    /**
     * 自底向上
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 1; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        // 没有结果
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    /**
     * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        // 要凑出金额i，有dp[i]种方式
        int[] dp = new int[amount + 1];
        // 设置起始状态，凑成0元的方案有一种
        dp[0] = 1;
        // 所有的状态
        for (int coin : coins) {
            // 所有的选择
            // 记录每添加一种面额的零钱，总金额j的变化
            for (int j = coin; j <= amount; j++) {
                // 在上一种零钱状态的基础上增大
                // 例如对于总额5，当只有面额为1的零钱时，只有一种可能 5x1
                // 当加了面额为2的零钱时，除了原来的那一种可能外
                // 还加上了组合了两块钱的情况，而总额为5是在总额为3的基础上加上两块钱来的
                // 所以就加上此时总额为3的所有组合情况
                // 状态转移方程
                dp[j] = dp[j] + dp[j - coin];

            }
        }
        return dp[amount];
    }

    /**
     * 300
     * 给定数组中的数字，找出指定
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // dp[i] 的值代表 nums 前 i 个数字的最长子序列长度
        int[] dp = new int[nums.length];
        int res = 0;
        // 初始值为1
        Arrays.fill(dp, 1);
        // 所有状态
        for (int i = 0; i < nums.length; i++) {
            // 所有选择，选择的就是i前面的串
            for (int j = 0; j < i; j++) {
                // nums[i]表示第i个元素
                if (nums[j] < nums[i]) {
                    // nums[j] < nums[i]时
                    // nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为dp[j]+1
                    // 为什么直接+1?因为默认dp[j]已经是上升子序列了，dp[j]是dp[i]的子问题
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 返回dp列表最大值，即可得到全局最长上升子序列长度
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        ReadMe readMe = new ReadMe();
//        int[] coins = new int[]{1, 2, 5};
//        System.out.println(readMe.coinChange(coins, 11));
        int[] arr = new int[] {10,9,2,5,3,7,101,18};
        System.out.println(readMe.lengthOfLIS(arr));
    }
}
